#include <iostream>
#include <vector>
using namespace std;

int solve(vector<int>&TOChange,int TChange)
{
    //Create DP array
    int n = TOChange.size();
    vector<vector<int>> dp(n+1,vector<int>(TChange+1));
    //The outer loop repersents traversal groups
    for(int i = 1;i<=n;++i)
    {
        for(int j = 1;j<=TChange;++j)
        {
            if(j-TOChange[i-1]>=0)
            {
                dp[i][j] = min(dp[i][j-1],dp[i][j-TOChange[i]])+1;
            }
        }
    }
    return dp[n][TChange];
}

int main()
{
    cout<<"Types of change:"<<endl;
    vector<int> TOChange({33,24,12,5,1});
    for(int cion:TOChange)
    {
        cout<<cion<<' ';
    }
    cout<<endl;
    cout<<"Total change: ";
    int TChange = 0;
    cin>>TChange;
    int ret = solve(TOChange,TChange);
    cout<<"solve:"<<ret<<endl;
    return 0;
}
